COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	RECURSION
C00009 ENDMK
C⊗;
RECURSION


	The idea of recursion is involved in several related concepts
in mathematics and computer science.

Recursion relation

	One or more functions of an integer variable is defined by giving
initial values and by giving the value for larger integers in terms of
smaller ones.  No single definition is generally accepted, so we shall
give examples of increasing complexity.

	1. The Fibonacci sequence is given by the equations

	f↓0 = 1

	f↓1 = 1

	f↓n+1 = f↓n + f↓n-1.

	2. When differential equations are to be solved numerically,
recursion relations such as

	f(x↓0 + nh) = F(f(x↓0 + (n-1)h),f(x↓0 + (n-2)h),...,f(x↓0 + (n-k)h))

arise where  f  is in general a vector of real numbers.

	3. When linear differential equations are solved by series, recursion
relations for the coefficients of the powers of the independent variables arise.

Recursive functions

	The systematic study of recursion began in the 1920's when mathematical
logic began to treat questions of definability, computability and decidability.
An important role is played by primitive recursive functions defined as
follows:

	a. Integer constants are primitive recursive.

	b. x↓i is a primitive recursive function of a set of arguments including
x↓i.

	c. Addition and multiplication are primitive recursive.

	d. Functions obtained from primitiver recursive functions by composition
are primitive recursive.

	e. If g and h are primitive recursive functions of n-1 and n+1 arguments
respectively, and f is defined by the relations

	f(0,x↓2,...,x↓n) = g(x↓2,...,x↓n)

	f(x↓1 + 1,x↓2,...,x↓n) = h(f(x↓1,...,x↓n),x↓1,...,x↓n),

then f is primitive recursive.

	g. A function is primitive recursive only if it follows from the previous
rules that it is.

	All the common functions of number theory are primitive recursive.
Moreover, many important functions on other countable domains than the
integers correspond to primitive recursive functions when we choose a specific
enumeration for the domain.

	Primitive recursive functions are a proper subset of general recursive
functions.  The definition of general recursive function is like that given above
for primitive recursive functions except that the relations  e  are replaced
by an arbitrary finite collection of equations relating the values of f
for different arguments, and the function is considered defined if and only
if a unique value of f(x↓1,...,x↓n) can be deduced from the equations for
each n-tuplet (x↓1,...,x↓n).  Naturally, if somone gives you an arbitrary
collection of such relations, you may not be able to determine whether
f(x↓1,...,x↓n) is uniquely determined, so you may not know whether you have
a general recursive function or not.  This difficulty is unavoidable.  There is
no  way to give a definition scheme that is always guaranteed to give a function
but which will give all computable functions.

	An important result for computer science is that the general recursive
functions co-incide with the functions defined by Turing machines which are
a simple form of computer.  They also co-incide with the functions of
integers defined by Algol or Fortran programs assuming that the program can
cope with whatever size integers arise.

	The study of computable functions is the domain of recursive function
theory, an active branch of mathematics.  The connection between current research
in recursive function theory and computing practice or even current research
in computer science is rather tenuous.  This situation might change because
of developments in either field.


Recursive procedures

	In programming, it is frequently convenient to have a procedure use
itself as a subprocedure.  If the procedure does this, it is called recursive.
As far as programming languages are concerned, recursive procedures are quite
natural; it requires a special statement in the definition of the language
to forbid them.  However, implementing them requires that a special kind
of object code be compiled, and early programming languages like FORTRAN
don't do it.  The problem is that variables in the program correspond to
locations in the machine, and when the program is called by itself, it
will use these same locations forgetting their previous contents.